package com.now.doublepointer;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 19. 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 */
public class RemoveNthFromEnd {
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode data = head;
        int i = 0;
        while (data.next != null) {
            data = data.next;
            i++;
        }
        // 只有一个节点，还需要删除时
        if (i == 0) {
            return null;
        }
        // 删除第一个节点
        if(i==n-1){
            return head.next;
        }
        int j = 0;
        ListNode deletePre = head;
        ListNode deleteNext = deletePre.next.next;
        while (j != i - n) {
            deletePre = deletePre.next;
            deleteNext = deletePre.next.next;
            j++;
        }

        deletePre.next = deleteNext;
        return head;
    }

    /**
     * 官方解答
     * 在遍历链表的同时将所有节点依次入栈。
     * 根据栈「先进后出」的原则，我们弹出栈的第 nn 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2));
        int n = 1;
        removeNthFromEnd(head, n);
    }
}


